Search results for "completeness theorem"
showing 10 items of 14 documents
Lambda substitution algebras
1993
In the paper an algebraic metatheory of type-free λ-calculus is developed. Our version is based on lambda substitution algebras (λSAs), which are just SAs introduced by Feldman (for algebraizing equational logic) enriched with a countable family of unary operations of λ-abstraction and a binary operation of application. Two representation theorems, syntactical and semantic, are proved, what directly provides completeness theorems.
Performability of Actions
2021
AbstractAction theory may be regarded as a theoretical foundation of AI, because it provides in a logically coherent way the principles of performing actions by agents. But, more importantly, action theory offers a formal ontology mainly based on set-theoretic constructs. This ontology isolates various types of actions as structured entities: atomic, sequential, compound, ordered, situational actions etc., and it is a solid and non-removable foundation of any rational activity. The paper is mainly concerned with a bunch of issues centered around the notion of performability of actions. It seems that the problem of performability of actions, though of basic importance for purely practical ap…
The double-incompleteness theorem
1976
Let T be a strong enough theory, and M - its metatheory, both are consistent. Then there is a closed arithmetical formula H that is undecidable in T, but one cannot prove in M neither that H is T-unprovable, nor that H is T-unrefutable. For English translation and proof, see K. Podnieks What is mathematics: Godel's theorem and around.
Realism, metamathematics, and the unpublished essays
1995
This initial chapter is divided into two sections. The first is devoted to a brief exposition of the intuitive essence and the philosophical motivation of Godel’s main metamathematical results, namely his completeness theorem for elementary logic (1930) and his incompleteness theorems for arithmetic (1931). Thereafter some discussion of the different ways to confront the relationship between those results and Godel’s philosophical realism in logic and mathematics is offered. Thus, mathematical realism will be successively regarded as (i) a philosophical consequence of those results; (ii) a heuristic principle which leads to them; (iii) a philosophical hypothesis which is “verified” by them.…
Protoalgebraicity and the Deduction Theorem
2001
This chapter is intended as an introduction to the Deduction Theorem and to applications of this theorem in metalogic.
Deontology of Compound Actions
2018
This paper, being a companion to the book [2] elaborates the deontology of sequential and compound actions based on relational models and formal constructs borrowed from formal linguistics. The semantic constructions presented in this paper emulate to some extent the content of [3] but are more involved. Although the present work should be regarded as a sequel of [3] it is self-contained and may be read independently. The issue of permission and obligation of actions is presented in the form of a logical system . This system is semantically defined by providing its intended models in which the role of actions of various types (atomic, sequential and compound ones) is accentuated. Since the…
Phenomenological-Semantic Investigations into Incompleteness
2000
When today the phenomenologist surveys the history of the philosophical comprehension of Godel’s theorems, he is confronted with the realization that the decisive publications come almost exclusively from the sphere of analytic philosophy.1 But does phenomenology in the spirit of Husserl not mean to keep in step with the epochal results of the special sciences by working on the phenomenological understanding of them? Phenomenological research of this kind means the same as development of phenomenological theory of science (Wissenschaftstheorie). In connection with the incompleteness theorems, the latter would be confronted with fundamental questions such as, “To what extent can mathematical…
Logic, Computing and Biology
2015
Logic and Computing are appropriate formal languages for Biology, and we may well be surprised by the strong analogy between software and DNA, and between hardware and the protein machinery of the cell. This chapter examines to what extent any biological entity can be described by an algorithm and, therefore, whether the Turing machine and the halting problem concepts apply. Last of all, I introduce the concepts of recursion and algorithmic complexity, both from the field of computer science, which can help us understand and conceptualise biological complexity.
Inductive inference of recursive functions: Qualitative theory
2005
This survey contains both old and very recent results in non-quantitative aspects of inductive inference of total recursive functions. The survey is not complete. The paper was written to stress some of the main results in selected directions of research performed at the University of Latvia rather than to exhaust all of the obtained results. We concentrated on the more explored areas such as the inference of indices in non-Goedel computable numberings, the inference of minimal Goedel numbers, and the specifics of inference of minimal indices in Kolmogorov numberings.
Introduction to Mathematical Logic (Edition 2017)
2017
Hyper-textbook for students in mathematical logic, Edition 2017